perm filename RJB[1,RWF] blob
sn#808397 filedate 1986-01-30 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 TO: Richard Beigel
C00003 ENDMK
C⊗;
TO: Richard Beigel
FROM: Bob Floyd
RE: proof by recursion
The proof by recursion theorem goes this way:
(1) Parameterless program determines its own index, n.
(2) Determine, using ≤k queries, whether phi↓n()↓. If yes, loop.
If no, print O (or something) and halt. Absurd.
RWF
The idea is that of Rice's Theorem, which can probably be generalized
to suit your purposes.